
\section{Preliminaries}\label{sec:preliminaries}



\subsubsection{Consistency in the projections}
Another desired, though not necessary, requirement of such online PCA algorithms is that $y_i$ is not ``too much different'' from $y_{i+1}$. Notice that in the optimal offline algorithm, $y_i = U_k^\top x_i,$ i.e., the same projection $U_k$ is used for the entire collection of vectors. In the online setting, let 
$y_i = U_i^\top x_i,$ i.e., $U_i$ is the projection matrix used for $x_i$. We require that
$U_{i+1}$ has the same number of non-zero columns as $U_i$ and maybe a few more. In other words, once a ``direction'' is added in the projection matrix it is never taken back. 

\subsection{sketching algorithm}
We review the PCA sketching algorithm of \zk{cite Edo}. The algorithm is given a parameter $\ell$ and is fed a stream of columns $r_t$ from of dimension $d$. It maintains a matrix $Z_t$ of $\ell$ columns in $\R^d$ that is a proxy of the matrix $R_t$ consisting of the $t$ columns $r_1,\ldots,r_t$.
\begin{Lem} \label{lem:sketch prop} [\zk{cite Edo, thm ?, implicit in the proof}]
\begin{itemize}
\item In any time point $t$ we have that
$$Z_t Z_t^\top \preceq R_t R_t^\top \preceq Z_t Z_t^\top + \|R_t\|_F^2/\ell$$
\item Assume that at time $t$, $u$ is an singular vector of $Z_t$ with singular value $\sigma$ and from that point on $\ip{r_{t'},u} =0$ for all $t' > t$. Then $u$ continues to be a singular vector of $Z_{t'}$ for all $t \geq t'$, with singular value $\sigma_{t'} \leq \sigma$ (possibly $\sigma_{t'}=0$).
\item an update of the sketch requires an amortized $O(d\ell)$ arithmetic operations.
\end{itemize}
\end{Lem}

\subsection{The ski-rental problem}
Our online algorithm for PCA was motivated by the simple ``break-even'' algorithm for the so-called ski-rental problem. 

